class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        # if not pHead1:
        #     return pHead2
        # if not pHead2:
        #     return pHead1
        # new_list_head = ListNode(-1)
        # new_list = new_list_head
        # while pHead1 and pHead2:
        #     if pHead1.val <= pHead2.val:
        #         new_list.next = pHead1
        #         pHead1 = pHead1.next
        #     else:
        #         new_list.next = pHead2
        #         pHead2 = pHead2.next
        #     new_list = new_list.next
        # if pHead1:
        #     new_list.next = pHead1
        # if pHead2:
        #     new_list.next = pHead2
        # return new_list_head.next
        '''
        递归版本
        :param pHead1:
        :param pHead2:
        :return:
        '''
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val <= pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)# 每次确定一个点！！！！
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1, pHead2.next)
            return pHead2